The present invention relates to techniques for providing a cache for query results that may adapt the cache-space utilization to the popularity of the various topics represented in the query stream.
Caching of search results is often employed in information retrieval systems and Web search engines to expedite query processing and reduce back-end server workload. Caching is a fundamental architectural optimization strategy, and query-result caching is important for Web search efficiency. Result caching, as its name implies, stores the results of some selected user queries in a fast-access memory (cache) for future reuse. When a query is requested, the cached results are directly returned to the user without reprocessing the request. Result caching improves the main efficiency-performance metrics of search engines, namely, latency and throughput. Indeed, serving a query with previously cached results decreases the latency perceived by the user as well as avoids the usage of computational resources with a consequent improvement of the search engine throughput.
Another advantage of caching query results is the reduction of energy consumption as cached queries do not need to be reprocessed by the back-end servers. Although other energy-efficiency optimization schemes exist, these approaches are complementary to result caching and not a contradictory alternative. Given desired and imposed “Green Policy” restrictions and the significant economic benefits due to the energy conservation, the interest of the search industry in energy saving is high. Energy wise, the cost of a cached query is typically assumed to be close to nothing, while a search of a query costs proportionally to its processing time in combination with the electricity price at the time of processing.
The main challenge in result caching is the identification of those queries whose results should be cached. However, via query log mining, high temporal locality may be observed in the query stream, enabling effective search-engine side caching of popular query results, such as, results of queries frequently requested in the past by different users. The result cache can be static or dynamic. A static cache is periodically populated in an offline manner, with the results of past, most-popular queries. Query popularity is estimated observing previously submitted queries in Web or other related search logs; a simplifying, but not always correct, core assumption is that queries popular in the past remain popular in the future. A dynamic cache, as the name suggests, is dynamically updated; when the cache is full and a new element is to be stored, an eviction/replacement policy is applied to decide which cache element must be removed to make space for the new one. The most common replacement policy for dynamic caches is the Least Recently Used (LRU) strategy: every time a query is submitted, the cache is updated, keeping track of what query was used and when; if necessary, the cache entry used least recently is evicted to vacate space for the new entry. The LRU strategy is effective without global knowledge and captures the “bursty” behavior of the queries by keeping recent queries in the cache and replacing those queries that are not requested for a long period of time.
Static and dynamic caches can be combined together. For example, in a Static-Dynamic Cache (SDC), the cache space is divided into two portions. The static portion stores results of the most popular queries. The dynamic portion maintains currency by applying LRU or other replacement strategies, for example, but not limited to, First In First Out (FIFO). This hybrid approach has proved successful in improving the performance of result caching with respect to both static and dynamic caching solutions in isolation. Despite its good performance, SDC suffers from some issues. Static caching captures highly frequent queries, while dynamic caching captures bursts of recently submitted queries. That is, static caching captures past queries that are popular over a relatively large time span (such as days or weeks) while dynamic caching might fail to capture such long-term temporal locality, but does capture short-term popularity. However, a query might not be sufficiently globally popular to be cached in the static cache and not be requested so frequently within a burst mode to be kept in the dynamic cache, but it might become relatively popular over a specific time interval, say a few hours in the early morning or several weekday evening hours. For example, a query on a specific topic, such as weather forecast, is typically submitted in the early morning hours or at the end of a work day, but relatively seldom in the remaining hours of a day.
Accordingly, a need arises for techniques that provide caching of queries that are not sufficiently globally popular to be cached in a static cache and are not requested frequently enough within a short time interval, namely are not sufficiently “bursty”, to be kept in a dynamic cache.